package 动态规划.经典动态规划题目.正则表达式;

import java.util.HashMap;
import java.util.Map;

public class 正则表达式_10 {
    public static void main(String[] args) {
        正则表达式_10 z = new 正则表达式_10();
        System.out.println(z.isMatch("ab", ".*c"));
    }

    public boolean isMatch(String A, String B) {
        int m = A.length() + 1;
        int n = B.length() + 1;
        //dp[i][j] 代表 A的前 i 个字符和 B 的前 j 个字符能否匹配
        boolean[][] dp = new boolean[m][n];

        //base case
        //空串和空串肯定能匹配,dp[0][1]和dp[1][0]~dp[s.length][0]默认值为false所以不需要显式初始化
        dp[0][0] = true;
        //填写第一行dp[0][2]~dp[0][p.length]
        for (int k = 2; k <= B.length(); k++) {
            //p字符串的第2个字符是否等于'*',此时j元素需要0个，所以s不变,减除p的*号以及*号前 这两个字符
            dp[0][k] = B.charAt(k - 1) == '*' && dp[0][k - 2];
        }
        // 状态转移：填写dp数组剩余部分
        //之所以下标都从1开始，是因为下标0代表的是空串，而两个字符串的空串情况我们在上面已经初始化完了，现在考虑的是二者都不为空串的情况
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                //匹配串的第j个字符是否为* :注意字符串的第一个字符，应该是j-1,因为dp数组的0，留给了空串
                if (B.charAt(j - 1) == '*') {
                    //将字符组合 B[j - 2] * 看作出现 0 次时，能否匹配
                    if (dp[i][j - 2]) {
                        dp[i][j] = true;
                    }
                    //让字符 B[j - 2] 多出现 1 次时，能否匹配；
                    else if (dp[i - 1][j] && A.charAt(i - 1) == B.charAt(j - 2)) {
                        dp[i][j] = true;
                    }
                    //让字符 '.' 多出现 1 次时，能否匹配；
                    else if (dp[i - 1][j] && B.charAt(j - 2) == '.') {
                        dp[i][j] = true;
                    }

                } else {
                    if (dp[i - 1][j - 1] && A.charAt(i - 1) == B.charAt(j - 1)) {
                        dp[i][j] = true;  // 1.即让字符 B[j - 1] 多出现一次时，能否匹配；
                    } else if (dp[i - 1][j - 1] && B.charAt(j - 1) == '.') {
                        dp[i][j] = true;         // 2.即将字符 . 看作字符 A[i - 1] 时，能否匹配；
                    }
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}
